Phase transitions for binomial sets under linear forms

Abstract: We generalize results on sum and difference sets of a subset S of $\mathbb{N}$ drawn from a binomial model. Given $A \subseteq \{0, 1, \dots, N\}$, an integer $h \geq 2$, and a linear form $L: \mathbb{Z}^h \to \mathbb{Z}$ $$L(x_1, \dots, x_h)\ :=\ u_1x_1 + \cdots + u_hx_h, \quad u_i \in \mathbb{Z}_{\neq 0} {\rm\ for\ all\ } i \in [h],$$ we study the size of $$L(A)\ =\ \left\{u_1a_1 + \cdots + u_ha_h : a_i \in A \right\}$$ and its complement $L(A)^c$ when each element of $\{0, 1, \dots, N\}$ is independently included in $A$ with probability $p(N)$, identifying two phase transitions. The first global one concerns the relative sizes of $L(A)$ and $L(A)^c$, with $p(N) = N^{-\frac{h-1}{h}}$ as the threshold. Asymptotically almost surely, below the threshold almost all sums generated in $L(A)$ are distinct and almost all possible sums are in $L(A)^c$, and above the threshold almost all possible sums are in $L(A)$. Our asymptotic formulae substantially extends work of Hegarty and Miller, resolving their conjecture. The second local phase transition concerns the asymptotic behavior of the number of distinct realizations in $L(A)$ of a given value, with $p(N) = N^{-\frac{h-2}{h-1}}$ as the threshold and identifies (in a sharp sense) when the number of such realizations obeys a Poisson limit. Our main tools are recent results on the asymptotic enumeration of partitions, Stein's method for Poisson approximation, and the martingale machinery of Kim-Vu.

Mathematics

Audience: researchers in the topic

( paper | slides )

Combinatorial and additive number theory (CANT 2025)